﻿package Hash_Func;

import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.util.ArrayList;
import java.util.Scanner;

/**
 *
 * @author Гамзатов
 */
public class Hash {
    
    public 
            int size = 1000;  // массив
            int c = 0;   // внесенные элементы

    public Hash() {
    }
    
    public void Making(String str) {
        try {
            // массив списков
            ArrayList[] ar = new ArrayList[size];  // слова
            ArrayList[] count = new ArrayList[size];  // повторения
            
            for(int i = 0; i < ar.length; i++) {
                ar[i] = new ArrayList();
                count[i] = new ArrayList(); 
            }
            
            String word;
            String ss;
            int ch, m;
            
            // поток из строки ss для считывания слов
            Scanner s;

            // читаем из файла строки
            BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream(str),("Windows-1251")));
            
            while((ss = br.readLine())!= null) {
                // фильтруем знаки
                for(int i = 0; i < ss.length(); i++)
                if((ss.charAt(i) =='.')||(ss.charAt(i) ==',')||(ss.charAt(i) == '-')||(ss.charAt(i)== '!')||(ss.charAt(i)== '?')||(ss.charAt(i)== ')')||(ss.charAt(i)== '(')||(ss.charAt(i)== ':')||(ss.charAt(i)== ';'))
                    ss = ss.substring(0, i) + ss.substring(i+1);

                s = new Scanner(ss);

                while(s.hasNext()) {
                    word = s.next();
                    int code = Hashh(word);  // хеш-функция для слова
                    
                    if(ar[code].isEmpty()) {
                        ar[code].add(word);
                        count[code].add(1);
                        c++;
                    }
                    else {
                        ch = ar[code].indexOf(word);
                        if(ch == -1)
                        {
                            ar[code].add(word);
                            count[code].add(1);
                            c++;
                        }
                        else {
                            m = (int)count[code].get(ch);
                            count[code].set(ch, m+1);
                        }
                    }
                }
                
                //обработка ресайза по массиву слов
                if(c/size > 1.2) {
                    c = 0;  // обнуляем счетчик элементов
                    size += 1000;  // увеличиваем массив
                    
                    // создаем массив списков
                    ArrayList[] aro = new ArrayList[size];  // слова
                    ArrayList[] counto = new ArrayList[size];  // повторения
                    
                    for(int i = 0; i < aro.length; i++) {
                        aro[i] = new ArrayList();
                        counto[i] = new ArrayList(); 
                    } 
                    
                    // применение хэш-функции
                    int h; String sl;
                    for(int i = 0; i < (size - 1000); i++) {
                        for(int j = 0; j < ar[i].size(); j++) {
                            sl = ar[i].get(j).toString();  // текущее слово
                            h = Hashh(sl);  // его хэш-значение
                            
                            if(aro[h].isEmpty()) {
                                aro[h].add(sl);
                                counto[h].add(count[i].get(j));
                                c++;
                            }
                            else {
                                ch = aro[h].indexOf(sl);
                                // такого слова нет в списке
                                if(ch == -1) {
                                    aro[h].add(sl);
                                    counto[h].add(count[i].get(j));
                                    c++;
                                }
                            }
                        }
                    }

                    // присваеваем старым массивам ссылки на новые
                    ar = aro;
                    count = counto;
                }
            } 
            br.close(); 
            
            // вывод
            for(int i = 0; i < size; i++) {
               for(int j = 0; j < ar[i].size(); j++) {
                   System.out.println(ar[i].get(j) + " - " + count[i].get(j) + " раз");
               }
            }
         }
       
        catch(java.io.IOException e) {
            e.printStackTrace();
        }
     } 
     
     public int Hashh(String word) {
             int h = 0; int mult = 32;
             for(int i = 0; i < word.length(); i++) {
                 h = (mult * h + Math.abs((int)word.charAt(i)-1038)) % size;  // кодировка начиная с номера 1040
             }
             
             return h;
         }
     
     public int Hashh1(String word) {
             int h = 0; int mult = 60;
             for(int i = 0; i < word.length(); i++) {
                 h = (mult * h + Math.abs((int)word.charAt(i)-1038)) % size;  // кодировка начиная с номера 1040
             }
             
             return h;
         }
     
     public int Hashh2(String word) {
             int h = 0; int mult = 1;
             for(int i = 0; i < word.length(); i++) {
                 h = (mult * h + Math.abs((int)word.charAt(i)-1038)) % size;  //кодировка начиная с номера 1040
                 mult += 3;
             }
             return h;
         }
     
     // проверяем эффективность для данного числа элементов в массиве
     public void Potency(int siz, String str) {   
         try {
            size = siz;
            int qlz = 0;  // счетчик коллизий
            
            // создаем массив списков
            ArrayList[] ar = new ArrayList[size];  // слова 
            ArrayList[] count = new ArrayList[size];  // повторения

            for(int i = 0; i < ar.length; i++) {
                ar[i] = new ArrayList();
                count[i] = new ArrayList(); 
            }

            String ss; String word; int ch, m, code;
            
            // поток из строки ss для считывания слов
            Scanner s;

            // читаем из файла строки
            BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream(str),("Windows-1251")));
            
            
            // для первой функции
            while((ss = br.readLine())!= null) {
                // фильтруем знаки
                for(int i = 0; i < ss.length(); i++)
                if((ss.charAt(i) =='.')||(ss.charAt(i) ==',')||(ss.charAt(i) == '-')||(ss.charAt(i)== '!')||(ss.charAt(i)== '?')||(ss.charAt(i)== ')')||(ss.charAt(i)== '(')||(ss.charAt(i)== ':')||(ss.charAt(i)== ';'))
                    ss = ss.substring(0, i) + ss.substring(i+1);  //удаление i-го элемента

                s = new Scanner(ss);

                //считали очередное слово из строки
                while(s.hasNext()) {
                    word = s.next();
                    code = Hashh(word);  // хеш-функция для слова
                    if(ar[code].isEmpty()) {
                        ar[code].add(word);
                        count[code].add(1);
                        c++;
                    }
                    else {  // коллизия
                        qlz++;
                        ch = ar[code].indexOf(word);
                        if(ch == -1) {  // такого слова нет в списке
                            ar[code].add(word);
                            count[code].add(1);
                            c++;
                        }
                        else {  // слово есть
                            m = (int)count[code].get(ch);
                            count[code].set(ch, m+1);
                        }
                    }
                }
                
            } 
            br.close(); 
            System.out.println("\nNumber of collusions of the Hashh method is " + qlz);
            
            
            // для второй функции
            qlz = 0;
            for(int i = 0; i < ar.length; i++) {
                ar[i] = new ArrayList();
                count[i] = new ArrayList(); 
            }

            BufferedReader br1 = new BufferedReader(new InputStreamReader(new FileInputStream(str),("Windows-1251")));

            while((ss = br1.readLine())!= null) {
                // фильтруем знаки
                for(int i = 0; i < ss.length(); i++)
                if((ss.charAt(i) =='.')||(ss.charAt(i) ==',')||(ss.charAt(i) == '-')||(ss.charAt(i)== '!')||(ss.charAt(i)== '?')||(ss.charAt(i)== ')')||(ss.charAt(i)== '(')||(ss.charAt(i)== ':')||(ss.charAt(i)== ';'))
                    ss = ss.substring(0, i) + ss.substring(i+1);  //удаление i-го элемента

                s = new Scanner(ss);

                // считали очередное слово из строки
                while(s.hasNext()) {
                    word = s.next();
                    code = Hashh1(word);  // хеш-функция для слова
                    if(ar[code].isEmpty()) {
                        ar[code].add(word);
                        count[code].add(1);
                        c++;
                    }
                    else {  // коллизия
                        qlz++;
                        ch = ar[code].indexOf(word);
                        if(ch == -1) {  // такого слова нет в списке
                            ar[code].add(word);
                            count[code].add(1);
                            c++;
                        }
                        else {  //слова есть
                            m = (int)count[code].get(ch);
                            count[code].set(ch, m+1);
                        }
                    }
                }
            } 
            br1.close(); 
            System.out.println("\nNumber of collusions of the Hashh1 method is " + qlz);
         
            
            // для третьей функции
            qlz = 0;
            for(int i = 0; i < ar.length; i++) {
                ar[i] = new ArrayList();
                count[i] = new ArrayList(); 
            }
            
            BufferedReader br2 = new BufferedReader(new InputStreamReader(new FileInputStream(str),("Windows-1251")));
            
            while((ss = br2.readLine())!= null) {
                // фильтруем знаки
                for(int i = 0; i < ss.length(); i++)
                if((ss.charAt(i) =='.')||(ss.charAt(i) ==',')||(ss.charAt(i) == '-')||(ss.charAt(i)== '!')||(ss.charAt(i)== '?')||(ss.charAt(i)== ')')||(ss.charAt(i)== '(')||(ss.charAt(i)== ':')||(ss.charAt(i)== ';'))
                    ss = ss.substring(0, i) + ss.substring(i+1);  // удаление i-го элемента
                s = new Scanner(ss);
                while(s.hasNext()) {  // считали очередное слово из строки
                    word = s.next();
                    code = Hashh2(word);  // хеш-функция для слова
                    if(ar[code].isEmpty()) {
                        ar[code].add(word);
                        count[code].add(1);
                        c++;
                    }
                    else {  // коллизия
                        qlz++;
                        ch = ar[code].indexOf(word);
                        if(ch == -1) {  // такого слова нет в списке
                            ar[code].add(word);
                            count[code].add(1);
                            c++;
                        }
                        else {  // слово есть
                            m = (int)count[code].get(ch);
                            count[code].set(ch, m+1);
                        }
                    }
                }
            } 
            br2.close(); 
            System.out.println("\nNumber of collusions of the Hashh2 method is " + qlz);
         }
         
        catch(java.io.IOException e)
        {
            e.printStackTrace();
        }
     }
}